package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 通配符匹配
    static class Solution {
        public boolean isMatch(String _s, String _p) {
            // 1) 边界处理与基本信息
            int n = _s.length();
            int m = _p.length();
            char[] s = _s.toCharArray();
            char[] p = _p.toCharArray();

            // 2) 创建 DP 表：dp[i][j] 表示 s[0..i-1] 是否能被 p[0..j-1] 匹配
            boolean[][] dp = new boolean[n + 1][m + 1];

            // 2.1 初始化：空串 vs 空模式
            dp[0][0] = true;

            // 2.2 初始化第一行：空串 vs 模式前缀
            for (int j = 1; j <= m; j++) {
                if (p[j - 1] == '*') {
                    // 只有当前缀全为 * 时才能匹配空串
                    dp[0][j] = dp[0][j - 1];
                } else {
                    dp[0][j] = false;
                }
            }

            // 3) 动态规划填表
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (p[j - 1] == s[i - 1] || p[j - 1] == '?') {
                        // 普通字符或 ? ：匹配当前一个字符，取决于前一位是否匹配
                        dp[i][j] = dp[i - 1][j - 1];
                    } else if (p[j - 1] == '*') {
                        // * 匹配空串：dp[i][j - 1]
                        // * 匹配一个或多个字符：dp[i - 1][j]
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                    }
                }
            }

            // 4) 返回最终结果
            return dp[n][m];
        }
    }
}